#pragma once

#include <string>
using std::string;

class exception
{
public:
	exception(int id, const string& errmsg);

	string what() const;

protected:
	int m_errid;
	string m_errmsg;
};


class matrix_coordinate_invalid : public exception
{
public:
	matrix_coordinate_invalid(const string& errmsg, int id = 1);
};

class matrix_multiplication_error : public exception
{
public:
	matrix_multiplication_error(const string& errmsg, int id = 2);
};

class matrix_addition_error : public exception
{
public:
	matrix_addition_error(const string& errmsg, int id = 3);
};


exception::exception(int id, const string& errmsg)
	: m_errid(id)
	, m_errmsg(errmsg)
{

}

string exception::what() const
{
	return m_errmsg;
}

matrix_coordinate_invalid::matrix_coordinate_invalid(const string& errmsg, int id)
	: exception(id, errmsg)
{

}

matrix_multiplication_error::matrix_multiplication_error(const string& errmsg, int id)
	: exception(id, errmsg)
{

}

matrix_addition_error::matrix_addition_error(const string& errmsg, int id)
	: exception(id, errmsg)
{

}


#pragma once

#include <vector>
using std::vector;

#include <iostream>
using std::cout;
using std::endl;
using std::cin;

#include <utility>



// 凡是在矩阵中的位置都以(1, 1)开始, 只有在存储中的位置才以0开始, 注意两种表述的不同, 此后不在强调

struct sparse_matrix_term
{
	// 位置信息
	int m_row;
	int m_col;
	// 数据信息
	int m_data;

	sparse_matrix_term(int row = 0, int col = 0, int data = 0);

	bool isvalid(int matrix_row, int matrix_col) const;
};

// 稀疏矩阵: COO压缩算法, 行存储
class sparse_matrix
{
public:
	// 默认构造
	sparse_matrix(int row = 0, int col = 0, int size = 0);

	// 拷贝构造
	sparse_matrix(const sparse_matrix& m2);

	// 清空
	void clear();

	// 赋值重载
	sparse_matrix& operator=(const sparse_matrix& x);

	// 析构, 不需要自定义

	// 添加元素
	void push(const sparse_matrix_term& term);

	// 修改sparse matrix的行列值
	void set_row_col(int row, int col);

	// 两个稀疏矩阵相加, 非直接或间接转换为二维数组形式计算
	/*
		有关两个稀疏矩阵相加算法的直观想象:
		想象两个完整的矩阵, 将这两个稀疏矩阵的非零元素标出来
		从第一行开始对两个矩阵同时进行逐行扫描, 遇到非零元素, 就相加到新矩阵中
	*/
	sparse_matrix& operator+=(const sparse_matrix& m2);


	// 获取在矩阵中位置为(row, col)的元素. 凡是写在矩阵中, 都是以(1,1)开始
	int get(int row, int col) const;

	// 输出矩阵, 以普通矩阵的形式
	void show();

private:
	// 矩阵的大小信息
	int m_row;
	int m_col;
	// 非零元素的信息, 行主映射
	vector<sparse_matrix_term> m_terms;
};

// 利用一个普通矩阵初始化稀疏矩阵
// 输入: 矩阵的行数n 矩阵的列数m 一个普通矩阵
void init_sparse_matrix_by_matrix(sparse_matrix& x);

// 利用非零元素初始化稀疏矩阵
// 输入: 矩阵的行数 矩阵的列数 矩阵中非零元素个数t
void init_sparse_matrix_by_nonzero_elements(sparse_matrix& x);


sparse_matrix_term::sparse_matrix_term(int row, int col, int data)
	: m_row(row)
	, m_col(col)
	, m_data(data)
{

}

bool sparse_matrix_term::isvalid(int matrix_row, int matrix_col) const
{
	if (m_col <= matrix_col && m_col >= 1 && m_row >= 1 && m_row <= matrix_row)
	{
		return true;
	}

	return false;
}

// 默认构造
sparse_matrix::sparse_matrix(int row, int col, int size)
	: m_row(row)
	, m_col(col)
	, m_terms(size, 0)
{

}

// 拷贝构造
sparse_matrix::sparse_matrix(const sparse_matrix& m2)
{
	m_row = m2.m_row;
	m_col = m2.m_col;
	m_terms = m2.m_terms;

}

// 清空
void sparse_matrix::clear()
{
	m_row = 0;
	m_col = 0;
	m_terms.clear();
}

// 赋值重载
sparse_matrix& sparse_matrix::operator=(const sparse_matrix& x)
{
	if (this != &x)
	{
		m_row = x.m_row;
		m_col = x.m_col;
		m_terms = x.m_terms;
	}

	return *this;
}

// 析构, 不需要自定义

// 添加元素
void sparse_matrix::push(const sparse_matrix_term& term)
{
	if (!term.isvalid(m_row, m_col))
	{
		throw matrix_coordinate_invalid("term coordinate invalid");
	}

	m_terms.push_back(term);
}

// 修改sparse matrix的行列值
void sparse_matrix::set_row_col(int row, int col)
{
	m_row = row;
	m_col = col;
}

sparse_matrix& sparse_matrix::operator+=(const sparse_matrix& m2)
{
	// 检查加法的合法性
	if (m_row != m2.m_row || m_col != m2.m_col)
	{
		throw matrix_addition_error("maxtri addition error");
	}

	// 对矩阵中的每一个元素进行, 行优先, 标号, 1,2,3...., 
	// 把矩阵看做一行

	sparse_matrix sum(m_row, m_col);
	
	int m1_count = 0;
	int m2_count = 0;
	while (m1_count < m_terms.size() && m2_count < m2.m_terms.size())
	{
		int m1_idx = (m_terms[m1_count].m_row - 1) * m_col + m_terms[m1_count].m_col;
		int m2_idx = (m2.m_terms[m2_count].m_row - 1) * m_col + m2.m_terms[m2_count].m_col;

		if (m1_idx < m2_idx)
		{
			sum.push(m_terms[m1_count]);
			++m1_count;
		}
		else if (m1_idx > m2_idx)
		{
			sum.push(m2.m_terms[m2_count]);
			++m2_count;
		}
		else
		{
			if (m_terms[m1_count].m_data + m2.m_terms[m2_count].m_data != 0)
			{
				sparse_matrix_term tmp(m_terms[m1_count].m_row, m_terms[m1_count].m_col, m_terms[m1_count].m_data + m2.m_terms[m2_count].m_data);
				sum.push(tmp);
				
			}

			++m1_count;
			++m2_count;
		}

	}

	while (m1_count < m_terms.size())
	{
		sum.push(m_terms[m1_count]);
		++m1_count;
	}

	while (m2_count < m2.m_terms.size())
	{
		sum.push(m2.m_terms[m2_count]);
		++m2_count;
	}

	m_terms.swap(sum.m_terms);

	return *this;
}



// 获取在矩阵中位置为(row, col)的元素. 凡是写在矩阵中, 都是以(1,1)开始
int sparse_matrix::get(int row, int col) const
{
	if (!(row >= 1 && row <= m_row && col >= 1 && col <= m_col))
	{
		throw matrix_coordinate_invalid("coordinate invalid");
	}

	for (int i = 0; i < m_terms.size(); ++i)
	{
		if (m_terms[i].m_row == row && m_terms[i].m_col == col)
		{
			return m_terms[i].m_data;
		}
		else if (m_terms[i].m_row > row)
		{
			break;
		}
		else if (m_terms[i].m_row == row && m_terms[i].m_col > col)
		{
			break;
		}
	}

	return 0; // 这一点就受限了该类的数据类型只能为数值型
}

// 输出矩阵, 以普通矩阵的形式
void sparse_matrix::show()
{
	cout << m_row << " " << m_col << endl;
	for (int i = 1; i <= m_row; ++i)
	{
		for (int j = 1; j <= m_col; ++j)
		{
			cout << get(i, j) << " ";

		}
		cout << endl;
	}
}

// 利用一个普通矩阵初始化稀疏矩阵
// 输入: 矩阵的行数n 矩阵的列数m 一个普通矩阵
void init_sparse_matrix_by_matrix(sparse_matrix& x)
{
	x.clear();
	int row = 0;
	int col = 0;
	cin >> row >> col;
	x.set_row_col(row, col);

	int val = 0;
	for (int i = 1; i <= row; ++i)
	{
		for (int j = 1; j <= col; ++j)
		{
			cin >> val;
			if (val != 0)
			{
				x.push(sparse_matrix_term(i, j, val));
			}
		}
	}

}

// 利用非零元素初始化稀疏矩阵
// 输入: 矩阵的行数 矩阵的列数 矩阵中非零元素个数t
void init_sparse_matrix_by_nonzero_elements(sparse_matrix& x)
{
	x.clear();
	int row = 0;
	int col = 0;
	int non_zero_num = 0; // 非零元素个数
	cin >> row >> col >> non_zero_num;
	x.set_row_col(row, col);

	// 载入非零元素
	int e_row = 0;
	int e_col = 0;
	int e_val = 0;
	for (int i = 0; i < non_zero_num; ++i)
	{
		cin >> e_row >> e_col >> e_val;
		x.push(sparse_matrix_term(e_row, e_col, e_val));
	}
}


void solution()
{
	// 输入: 操作个数 
	int op_num = 0;
	cin >> op_num;

	// 执行, 规定第一个操作为重置矩阵
	int opcode = 0; // 操作码
	sparse_matrix m1;

	for (int i = 0; i < op_num; ++i)
	{
		cin >> opcode;

		switch (opcode)
		{
			/*
				重置矩阵 1:
					输入: 矩阵的行数n 矩阵的列数m 一个普通矩阵

					执行: 按COO压缩算法存储该矩阵
			*/
			case 1:
			{
				init_sparse_matrix_by_matrix(m1);
				break;
			}
			
			/*
				矩阵加法 3: 
					输入: 矩阵的行数 矩阵的列数 矩阵中非零元素个数t
							按行优先给出t个非零元素的COO三元组
				
					执行以及输出: 设输入的矩阵为m2,若运算合法,则将运算结果矩阵赋给m1,若不合法,则将m2赋给m1, 输出 -1。
			*/
			case 3:
			{
				sparse_matrix m2;
				init_sparse_matrix_by_nonzero_elements(m2);
				try
				{
					m1 += m2;
					
				}
				catch (const exception& e)
				{
					m1 = m2;
					cout << -1 << endl;
				}

				break;
			}
			/*
				输出操作 4, 输出一个普通矩阵
			*/
			case 4:
			{
				m1.show();
				break;
			}
			
		}
	}


}

int main()
{
	solution();

	return 0;
}     